package org.xqh.study.leetcode.algorithm.slidewindow;

import org.xqh.study.leetcode.algorithm.UnionFind;

/**
 * @ClassName MinSwapsCouples
 * @Description 情侣牵手
 * <p>
 * https://leetcode-cn.com/problems/couples-holding-hands/
 * @Author xuqianghui
 * @Date 2021/2/14 20:48
 * @Version 1.0
 */
public class MinSwapsCouples {

    public static void main(String[] args) {
        int[] row = {0, 3, 2, 1, 4, 6, 5, 8, 7, 9};
        System.out.println(minSwapsCouples(row));
    }

    public static int minSwapsCouples(int[] row){

        int len = row.length;
        int n = len/2;
        UnionFind unionFind = new UnionFind(n);
        for(int i = 0; i < len; i += 2){
            System.out.println(row[i]/2+"," + row[i+1]/2);
            unionFind.union(row[i]/2, row[i+1]/2);
        }
        return n - unionFind.getCount();
    }


    public static int minSwapsCouples11(int[] row) {
        int len = row.length;
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            int num = row[i];
            arr[num] = i;
        }

        int res = 0;
        for (int j = 0; j < len / 2; j++) {
            int fIdx = 2 * j;
            int nextIdx = 2 * j + 1;
            int first = row[fIdx];
            int next = row[nextIdx];
            int compare = first % 2 == 0 ? first + 1 : first - 1;
            if(compare != next){
                res ++;//需要替换
                //找到 需要替换的数字 所在位置
                int comIdx = arr[compare];
                int tmp = row[comIdx];
                row[comIdx] = next;
                row[nextIdx] = tmp;
                arr[tmp] = nextIdx;
                arr[next] = comIdx;
            }
        }
        return res;
    }
}
